//https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/description/?envType=daily-question&envId=2024-04-06

class TreeAncestor {
public:
    TreeAncestor(int n, vector<int>& parent) {
        g.resize(n);
        fa.resize(n,vector<int>(20));
        dep.resize(n,0);
        for(int i=1;i<parent.size();i++)
            g[parent[i]].push_back(i);
        function<void(int,int)>dfs=[&](int cur,int father)->void{
            if(cur!=0)
                dep[cur]=dep[father]+1;
            fa[cur][0]=father;
            for(int i=1;i<20;i++)
                fa[cur][i]=fa[fa[cur][i-1]][i-1];
            for(int j=0;j<g[cur].size();j++)
                dfs(g[cur][j],cur);
        };
        dfs(0,0);
    }
    int getKthAncestor(int node, int k) {
        int h=dep[node]-k;
        for(int i=19;i>=0;i--)
        {
            if(dep[fa[node][i]]>=h)
                node=fa[node][i];
        }
        return dep[node]==h?node:-1;
    }
    vector<vector<int>>g;
    vector<vector<int>>fa;
    vector<int>dep;
};